/* 
 * File:   ShortestPath.hpp
 * Author: Francesco
 *
 * Created on 16 dicembre 2012, 20.11
 */

#ifndef SHORTESTPATH_HPP
#define	SHORTESTPATH_HPP

#include "DirectedGraph.hpp"
#include "DijkstraInfo.hpp"
#include "Vertex.hpp"
#include "SimpleGraph.hpp"
#include "VertexSet.hpp"

#include <map>
#include <vector>
#include <limits>
#include <queue>
#include <set>

using namespace std;

template <typename I>
class ShortestPath {
private:
    static void initializeSingleSource(DirectedGraph<I>* graph,
            vector<DijkstraInfo<I>*> *shortestPaths, Vertex<I>* source);
    static void relax(Edge<I>* edge, vector<DijkstraInfo<I>*> *shortestPaths);

public:
    static vector<DijkstraInfo<I>*>* dijkstra(DirectedGraph<I>* graph, Vertex<I>* source);
};

struct compare {

        template <typename I>
        bool operator()(DijkstraInfo<I>* l, DijkstraInfo<I>* r) {
        return l->getDistance() > r->getDistance();
    }
};

template <typename I> vector<DijkstraInfo<I>*>* ShortestPath<I>::dijkstra(DirectedGraph<I>* graph, Vertex<I>* source) {
    vector<DijkstraInfo<I>*> *paths = new vector<DijkstraInfo<I>*>();
    initializeSingleSource(graph, paths, source);

    std::set<Vertex<I>*> set;
    priority_queue<DijkstraInfo<I>*, vector<DijkstraInfo<I>*>, compare> queue;
    vector<Vertex<I>*> *vertices = graph->getVertices();

    typename std::vector<DijkstraInfo<I>*>::iterator itInfo;
    for (itInfo = paths->begin(); itInfo != paths->end(); ++itInfo) {
        queue.push(*itInfo);
    }

    while (!queue.empty()) {
        DijkstraInfo<I> *u = queue.top();
        queue.pop();
        set.insert(u->getCurrent());
        std::list<Edge<I>*>* adjacences = u->getCurrent()->getAdjacencyList();
        typename std::list<Edge<I>*>::iterator itEdges;
        for (itEdges = adjacences->begin(); itEdges != adjacences->end(); ++itEdges) {
            relax(*itEdges, paths);
        }
    }
    return paths;
}

template <typename I> void ShortestPath<I>::relax(Edge<I>* edge, vector<DijkstraInfo<I>*> *shortestPaths) {
    DijkstraInfo<I> *uInfo, *vInfo;

    int found = 0;
    int i = 0;
    while (found < 2 && i < shortestPaths->size()) {
        if (shortestPaths->at(i)->getCurrent() == edge->getFrom()) {
            uInfo = shortestPaths->at(i);
            found++;
        } else if (shortestPaths->at(i)->getCurrent() == edge->getTo()) {
            vInfo = shortestPaths->at(i);
            found++;
        }
        i++;
    }

    if (vInfo->getDistance() > uInfo->getDistance() + edge->getWeight()) {
        vInfo->setDistance(uInfo->getDistance() + edge->getWeight());
        vInfo->setParent(edge->getFrom());
    }
}

template <typename I> void ShortestPath<I>::initializeSingleSource(DirectedGraph<I>* graph,
        vector<DijkstraInfo<I>*> *shortestPaths, Vertex<I>* source) {
    vector<Vertex<I>*> *vertices = graph->getVertices();
    typename std::vector<Vertex<I>*>::iterator it;
    for (it = vertices->begin(); it != vertices->end(); ++it) {
        if ((*it)->getLabel() == source->getLabel()) {
            shortestPaths->push_back(new DijkstraInfo<I > (*it, 0, NULL));
        } else {
            shortestPaths->push_back(new DijkstraInfo<I > (*it, std::numeric_limits<int>::max(), NULL));
        }
    }

}
#endif	/* SHORTESTPATH_HPP */

